import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTree {
    class TreeNode{
        private char val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    //根据字符串 通过前序变量构建二叉树
    /*private int i=0;
    public TreeNode construct(String str){
        TreeNode treeNode=null;
        if(str.charAt(i)!='#'){
           treeNode=new TreeNode(str.charAt(i));
           i++;
           treeNode.left=construct(str);
           treeNode.right=construct(str);

        }else{
            i++;
        }
        //终止条件
        return treeNode;
    }*/
    //前序遍历并打印
    public void preorder(TreeNode root){
        if(root==null)return;
        System.out.print(root.val+" ");
        preorder(root.left);
        preorder(root.right);
    }

    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;//说明当前的root已经到null了
        if (root == p || root == q) return root;//遍历到p，q就返回给调用函数
        //递归，并且记录当前结点的左右孩子状态
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //此时的root判断左右孩子的状态
        //如果都不为null。说明p，q在当前结点的左右两侧处，则当前结点就是公共祖先
        if (left != null && right != null) {
            return root;
        } else if (left != null && right == null) {
            return left;//把最终结果传回去
        } else {
            return right;
        }
    }
    //
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q){
        if(root==null||p==null||q==null)return null;
        Stack<TreeNode>stack=new Stack<>();
        Stack<TreeNode>stack1=new Stack<>();
        path(root,p,stack);
        path(root,q,stack1);
        //判断栈的大小
        int len=Math.abs(stack.size()-stack1.size());
        if(stack.size()>stack1.size()){
            while (len!=0){
                stack.pop();
                len--;
            }
        }else {
            while (len!=0){
                stack1.pop();
                len--;
            }
        }
        //同时出栈
        while (!stack.isEmpty()&&!stack1.isEmpty()){
            if(stack.peek()==stack1.peek()){
                return stack.peek();
            }else{
                stack.pop();
                stack1.pop();
            }
        }
        return null;
    }
    //获取从根结点到某个结点的路径
    public boolean path(TreeNode root, TreeNode p, Stack<TreeNode>stack){
        //如果根、p为null返回false
        if(root==null||p==null)return false;
        //入栈(走到这里说明可以入栈)
        stack.push(root);
        //root就是p 终止遍历返回true
        if(root==p)return true;
        //遍历
        boolean left=path(root.left,p,stack);
        if(left){
            return true;//找到了p就开始一直往回走
        }
        boolean right=path(root.right,p,stack);
        if(right){
            return true;//找到了p就开始一直往回走
        }
        //走到这里说明，没找到p，把说明该结点不属于这个路径
        stack.pop();
        return false;
    }

    //中序遍历修改left right的值
    //记录前驱
    private TreeNode prev;
    public void inorder(TreeNode pRootOfTree){
        if(pRootOfTree==null)return;
        inorder(pRootOfTree.left);
        //修改当前结点的前驱
        pRootOfTree.left=prev;
        //修改前驱的后继
        if(prev!=null){//防止第一次空指针异常
            prev.right=pRootOfTree;
        }
        prev=pRootOfTree;//记录前驱
        inorder(pRootOfTree.right);
    }
    //二叉搜索树转为双向链表
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)return null;
        inorder(pRootOfTree);//建立双向链表
        //根据链表找到头结点
        //pRootOfTree是树的根结点
        TreeNode cur=pRootOfTree;
        while (cur.left!=null){
            cur=cur.left;
        }
        return cur;
    }

    //建树
    public int i=0;
    public TreeNode createTree(char[] preorder,char[] inorder,int ib,int ie){
        //结束条件 ib>ie时
        if(ib>ie)return null;
        //创建根结点
        //i表示前序数组当前元素
        TreeNode root=new TreeNode(preorder[i]);

        //通过中序数组划分左右子树在（ib和ie的范围内寻找）
        int ir=findIndex(preorder[i],inorder,ib,ie);
        i++;//移动

        //给root左右属性赋值
        //每一次递归ib，ie的值都会改变
        //根结点的左边，ie=ir-1；
        root.left=createTree(preorder,inorder,ib,ir-1);
        //根结点的右边，ib=ir+1；
        root.right=createTree(preorder,inorder,ir+1,ie);

        return root;//返回当前结点
    }
    public int findIndex(char tmp,char[] inorder,int ib,int ie){
        for (int j = ib; j <=ie ; j++) {
            if(tmp==inorder[j]){
                return j;
            }
        }
        return -1;
    }
    //前序遍历中序遍历构建二叉树
    public TreeNode buildTree(char[] preorder, char[] inorder) {
        int ie=inorder.length-1;
        return createTree(preorder,inorder,0,ie);
    }

//前序遍历
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character>list=new ArrayList<>();
        Stack<TreeNode>ret=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!ret.empty()){
            while (cur!=null){
                System.out.print(cur.val);
                list.add(cur.val);
                ret.push(cur);
                cur=cur.left;
            }
            cur=ret.pop().right;
        }
        return list;
    }

    //中序遍历
    public List<Character> inorderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        Stack<TreeNode> ret = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !ret.empty()) {
            while (cur != null) {
                ret.push(cur);
                cur = cur.left;
            }
            System.out.print(cur.val);
            list.add(cur.val);
            TreeNode tmp=cur;
            cur=tmp.right;
        }
        return list;
    }

    //后序遍历
    public List<Character> postorderTraversal(TreeNode root) {
        Stack<TreeNode>stack=new Stack<>();
        List<Character>ret=new ArrayList<>();
        TreeNode prev=null;//记录已经访问过的节点
        TreeNode cur=root;
        while (cur!=null||!stack.empty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode tmp=stack.peek();
            if(tmp.right==null||tmp.right==prev){
                ret.add(tmp.val);
                stack.pop();
                prev=tmp;//记录已经访问过的节点
            }else{
                cur=tmp.right;
            }
        }
        return ret;
    }
}
